The Complexity of Drawing Graphs on Few Lines and Few Planes

摘要

It is well known that any graph admits a crossing-free straight-line drawingin $\mathbb{R}^3$ and that any planar graph admits the same even in$\mathbb{R}^2$. For a graph $G$ and $d \in \{2,3\}$, let $\rho^1_d(G)$ denotethe minimum number of lines in $\mathbb{R}^d$ that together can cover all edgesof a drawing of $G$. For $d=2$, $G$ must be planar. We investigate thecomplexity of computing these parameters and obtain the following hardness andalgorithmic results. - For $d\in\{2,3\}$, we prove that deciding whether $\rho^1_d(G)\le k$ for agiven graph $G$ and integer $k$ is ${\exists\mathbb{R}}$-complete. - Since $\mathrm{NP}\subseteq{\exists\mathbb{R}}$, deciding $\rho^1_d(G)\lek$ is NP-hard for $d\in\{2,3\}$. On the positive side, we show that the problemis fixed-parameter tractable with respect to $k$. - Since ${\exists\mathbb{R}}\subseteq\mathrm{PSPACE}$, both $\rho^1_2(G)$ and$\rho^1_3(G)$ are computable in polynomial space. On the negative side, we showthat drawings that are optimal with respect to $\rho^1_2$ or $\rho^1_3$sometimes require irrational coordinates. - Let $\rho^2_3(G)$ be the minimum number of planes in $\mathbb{R}^3$ neededto cover a straight-line drawing of a graph $G$. We prove that deciding whether$\rho^2_3(G)\le k$ is NP-hard for any fixed $k \ge 2$. Hence, the problem isnot fixed-parameter tractable with respect to $k$ unless$\mathrm{P}=\mathrm{NP}$.